home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / programm.ing / falcon / nt_dsp1.lzh / NT_DSP1.MSA / FFT / FFTR2D.HLP < prev    next >
Encoding:
Text File  |  1990-01-17  |  3.4 KB  |  61 lines
  1.          Name: FFTR2D.ASM
  2.          Type: Assembler Macro
  3.       Version: 1.0
  4.   Last Change:  8-Aug-86
  5.  
  6.   Description: Radix 2, In-place, Decimation-in-time Complex FFT Macro
  7.  
  8.  This macro performs a complete Fast Fourier Transform (FFT) on complex
  9.  data.  The basic algorithm is the Decimation-in-time (DIT), Radix 2
  10.  FFT algorithm using 24 bit fixed-point arithmetic.  The algorithm uses
  11.  a full-cycle sinewave lookup table for the FFT coefficients (twiddle
  12.  factors).  The macro can be called to perform any FFT from 2-32768
  13.  points.  Simply call it with the arguments of number of FFT points,
  14.  location of the data array, the location of the sinewave table and the
  15.  number of points in the sinewave table.  Note that the size of the
  16.  sinewave table does not have to match the size of the FFT transform.
  17.  For example, a 256 point complex FFTR2D macro requires a sinewave
  18.  table of 256, 512, 768, 1024,.. points; that is, a multiple of 256
  19.  points.  For real FFT's, a 256 point real FFTR2D macro requires a
  20.  sinewave table of 128, 256, 384, 512,.. points; that is, one-half the
  21.  size required for a complex FFT.  This allows different size FFT's to
  22.  use a fixed size sinewave table, such as the DSP56001 Y Data ROM.
  23.  
  24.  All register initialization is performed by this macro.  However, the
  25.  macro assumes that registers which should not be altered by the FFT
  26.  have already been saved by the main program.  This allows the user to
  27.  fit the FFT macro into his application and thus control the context
  28.  switching overhead.  No data scaling is performed and no overflow
  29.  detection is done.  Modifications to this routine could allow it to
  30.  be used with the scaling modes and thus allow dynamic scaling for
  31.  each FFT pass.
  32.  
  33.  All data is complex, with the real part in X Data memory and the
  34.  imaginary part in Y Data memory.  For an N point FFT, the data buffer
  35.  requires N X Data and N Y Data memory locations.  The algorithm is
  36.  performed "in-place", meaning that only one data buffer is required
  37.  for both input and output data.  The input data is assumed to be in
  38.  normal (time-sequential) order and the output is in bit-reversed
  39.  order.  By using the reverse-carry address modifier and a separate
  40.  output data buffer, the output data may be easily unscrambled.  Other
  41.  methods also exist to unscramble the output data without a separate
  42.  output data buffer.  The FFTR2D macro uses "twiddle factors" (sine
  43.  table) stored in Y Data memory.  For maximum speed, the FFT macro
  44.  performs a lookup table operation to get new sine values for each
  45.  group of butterflies.  A SINEWAVE macro is available to generate
  46.  these tables.  For an N point FFT, N Y Data locations are required.
  47.  Sine values could be calculated in real-time to save data memory at
  48.  the expense of execution time.
  49.  
  50.  The FFTR2D macro requires about 40 words of program memory for any
  51.  size FFT from 2-32768 points.  The main advantage of this FFT routine
  52.  is its use of a full-cycle sinewave table for coefficients.  This
  53.  sinewave table can often be shared with other functions in the system
  54.  and is available in the DSP56001 Y Data ROM.  Using a 20.5 MHz
  55.  DSP56001, the FFTR2D macro can perform a 256 point complex FFT in
  56.  approximately 0.86 milliseconds.  Additional algorithm details are
  57.  included in the source file; however, more algorithm description
  58.  would be required for complete understanding by typical users.  The
  59.  test program FFTR2DT demonstrates the calling procedure for this
  60.  macro.
  61.